package main

// 非递归解法。题解中看到的， 可以应对，两数相加大于 int溢出的情况， 采用字符串相加
// 从问题给出的数据规模来看，这题就是暴力计算， 累加数列前两项确定，后面都会确定，
// 所以枚举前两项。另外就是 大数的运算， 字符串相加。

// 这里就是计算两个字符串（数）的 和（相加）
func add(a, b string) string {
	// 1. 将两个字符串表示的 数，进行相加。 res存储每位结果， one表示进位
	res, one := []byte{}, 0
	for i, j := len(a)-1, len(b)-1; i >= 0 || j >= 0; {
		curA, curB := 0, 0
		if i >= 0 {
			curA = int(a[i] - '0')
			i--
		}
		if j >= 0 {
			curB = int(b[j] - '0')
			j--
		}
		cur := curA + curB + one
		one = cur / 10
		res = append(res, byte(cur%10)+'0')
	}
	// 2. 如果最后还有进位， 添加上去
	if one == 1 {
		res = append(res, '1')
	}
	// 3. 最后反转，高位在前
	for i, n := 0, len(res); i < n/2; i++ {
		res[i], res[n-1-i] = res[n-1-i], res[i]
	}
	// 4. 返回字符串
	return string(res)
}

// 名字起的是dfs，但是没用到递归~~~
// 判断当前定位的前两个数开头，能否正确是 累加数列
func dfs(num string, first, second int) bool {
	// 前两个数的表示是 [last, first] [first, second] 三点分两个数，last表示在最前面的
	n, last := len(num), 0
	for second < n {
		// 1. 作为数字，不能拥有前导0， 所以，以0开头的，都直接报错！（除非长度为 1，就是数字0）
		if (num[last] == '0' && first > last+1) || (num[first] == '0' && second > first+1) {
			return false
		}
		// 2. 取前两个数相加
		s := add(num[last:first], num[first:second])
		// 3. 判断相加结果，是否在序列中
		// 		1. 如果长度超出序列， 2. 或者 计算结果 不等于 当前位置的 “第三个数”，返回false
		if second+len(s) > n || num[second:second+len(s)] != s {
			return false
		}
		// 4. 更新三个数，继续下一轮迭代判断
		last, first, second = first, second, second+len(s)
	}
	return true
}

func isAdditiveNumber(num string) bool {
	// 枚举所有的可能的前两个数， 找到合适的， 如果没有返回 false
	for i := 1; i < len(num)-1; i++ {
		for j := i + 1; j < len(num); j++ {
			if dfs(num, i, j) {
				return true
			}
		}
	}
	return false
}
